class Solution {
    public int mySqrt(int x) {
        if(x == 0) {
            return 0;
        }
        int left = 0;
        int rigth = x;
        int a = -1;
        while(left <= rigth) {
            int mid = left + (rigth - left) / 2;
            if((long)mid * mid <= x) {
                a = mid;
                left = mid + 1;
            } else {
                rigth = mid -1;
            }
        }
        return a;
    }
}